from typing import List


class Solution:
    def gobang(self, pieces: List[List[int]]) -> str:
        # ----- 整理已经落子的情况 -----
        already_black = set()
        already_white = set()
        for x0, y0, color in pieces:
            if color == 0:
                already_black.add((x0, y0))
            else:
                already_white.add((x0, y0))

        # ----- 枚举所有可能的获胜方案 -----

        # 从上到下、从左上到右下、从右上到左下、从左到右
        blacks = set()
        whites = set()

        for x0, y0, color in pieces:
            # 枚举黑色所有可能胜利的路径
            if color == 0:  # 黑色
                # 上下
                blacks.add(((x0 - 4, y0), (x0 - 3, y0), (x0 - 2, y0), (x0 - 1, y0), (x0 - 0, y0)))
                blacks.add(((x0 - 3, y0), (x0 - 2, y0), (x0 - 1, y0), (x0 - 0, y0), (x0 + 1, y0)))
                blacks.add(((x0 - 2, y0), (x0 - 1, y0), (x0 - 0, y0), (x0 + 1, y0), (x0 + 2, y0)))
                blacks.add(((x0 - 1, y0), (x0 - 0, y0), (x0 + 1, y0), (x0 + 2, y0), (x0 + 3, y0)))
                blacks.add(((x0 - 0, y0), (x0 + 1, y0), (x0 + 2, y0), (x0 + 3, y0), (x0 + 4, y0)))

                # 左上右下
                blacks.add(((x0 - 4, y0 - 4), (x0 - 3, y0 - 3), (x0 - 2, y0 - 2), (x0 - 1, y0 - 1), (x0 - 0, y0 - 0)))
                blacks.add(((x0 - 3, y0 - 3), (x0 - 2, y0 - 2), (x0 - 1, y0 - 1), (x0 - 0, y0 - 0), (x0 + 1, y0 + 1)))
                blacks.add(((x0 - 2, y0 - 2), (x0 - 1, y0 - 1), (x0 - 0, y0 - 0), (x0 + 1, y0 + 1), (x0 + 2, y0 + 2)))
                blacks.add(((x0 - 1, y0 - 1), (x0 - 0, y0 - 0), (x0 + 1, y0 + 1), (x0 + 2, y0 + 2), (x0 + 3, y0 + 3)))
                blacks.add(((x0 - 0, y0 - 0), (x0 + 1, y0 + 1), (x0 + 2, y0 + 2), (x0 + 3, y0 + 3), (x0 + 4, y0 + 4)))

                # 左右
                blacks.add(((x0, y0 - 4), (x0, y0 - 3), (x0, y0 - 2), (x0, y0 - 1), (x0, y0 - 0)))
                blacks.add(((x0, y0 - 3), (x0, y0 - 2), (x0, y0 - 1), (x0, y0 - 0), (x0, y0 + 1)))
                blacks.add(((x0, y0 - 2), (x0, y0 - 1), (x0, y0 - 0), (x0, y0 + 1), (x0, y0 + 2)))
                blacks.add(((x0, y0 - 1), (x0, y0 - 0), (x0, y0 + 1), (x0, y0 + 2), (x0, y0 + 3)))
                blacks.add(((x0, y0 - 0), (x0, y0 + 1), (x0, y0 + 2), (x0, y0 + 3), (x0, y0 + 4)))

                # 左下右上
                blacks.add(((x0 - 4, y0 + 4), (x0 - 3, y0 + 3), (x0 - 2, y0 + 2), (x0 - 1, y0 + 1), (x0 - 0, y0 + 0)))
                blacks.add(((x0 - 3, y0 + 3), (x0 - 2, y0 + 2), (x0 - 1, y0 + 1), (x0 - 0, y0 + 0), (x0 + 1, y0 - 1)))
                blacks.add(((x0 - 2, y0 + 2), (x0 - 1, y0 + 1), (x0 - 0, y0 + 0), (x0 + 1, y0 - 1), (x0 + 2, y0 - 2)))
                blacks.add(((x0 - 1, y0 + 1), (x0 - 0, y0 + 0), (x0 + 1, y0 - 1), (x0 + 2, y0 - 2), (x0 + 3, y0 - 3)))
                blacks.add(((x0 - 0, y0 + 0), (x0 + 1, y0 - 1), (x0 + 2, y0 - 2), (x0 + 3, y0 - 3), (x0 + 4, y0 - 4)))

            # 枚举白色所有可能胜利的点
            else:  # color == 1:  白色
                # 上下
                whites.add(((x0 - 4, y0), (x0 - 3, y0), (x0 - 2, y0), (x0 - 1, y0), (x0 - 0, y0)))
                whites.add(((x0 - 3, y0), (x0 - 2, y0), (x0 - 1, y0), (x0 - 0, y0), (x0 + 1, y0)))
                whites.add(((x0 - 2, y0), (x0 - 1, y0), (x0 - 0, y0), (x0 + 1, y0), (x0 + 2, y0)))
                whites.add(((x0 - 1, y0), (x0 - 0, y0), (x0 + 1, y0), (x0 + 2, y0), (x0 + 3, y0)))
                whites.add(((x0 - 0, y0), (x0 + 1, y0), (x0 + 2, y0), (x0 + 3, y0), (x0 + 4, y0)))

                # 左上右下
                whites.add(((x0 - 4, y0 - 4), (x0 - 3, y0 - 3), (x0 - 2, y0 - 2), (x0 - 1, y0 - 1), (x0 - 0, y0 - 0)))
                whites.add(((x0 - 3, y0 - 3), (x0 - 2, y0 - 2), (x0 - 1, y0 - 1), (x0 - 0, y0 - 0), (x0 + 1, y0 + 1)))
                whites.add(((x0 - 2, y0 - 2), (x0 - 1, y0 - 1), (x0 - 0, y0 - 0), (x0 + 1, y0 + 1), (x0 + 2, y0 + 2)))
                whites.add(((x0 - 1, y0 - 1), (x0 - 0, y0 - 0), (x0 + 1, y0 + 1), (x0 + 2, y0 + 2), (x0 + 3, y0 + 3)))
                whites.add(((x0 - 0, y0 - 0), (x0 + 1, y0 + 1), (x0 + 2, y0 + 2), (x0 + 3, y0 + 3), (x0 + 4, y0 + 4)))

                # 左右
                whites.add(((x0, y0 - 4), (x0, y0 - 3), (x0, y0 - 2), (x0, y0 - 1), (x0, y0 - 0)))
                whites.add(((x0, y0 - 3), (x0, y0 - 2), (x0, y0 - 1), (x0, y0 - 0), (x0, y0 + 1)))
                whites.add(((x0, y0 - 2), (x0, y0 - 1), (x0, y0 - 0), (x0, y0 + 1), (x0, y0 + 2)))
                whites.add(((x0, y0 - 1), (x0, y0 - 0), (x0, y0 + 1), (x0, y0 + 2), (x0, y0 + 3)))
                whites.add(((x0, y0 - 0), (x0, y0 + 1), (x0, y0 + 2), (x0, y0 + 3), (x0, y0 + 4)))

                # 左下右上
                whites.add(((x0 - 4, y0 + 4), (x0 - 3, y0 + 3), (x0 - 2, y0 + 2), (x0 - 1, y0 + 1), (x0 - 0, y0 + 0)))
                whites.add(((x0 - 3, y0 + 3), (x0 - 2, y0 + 2), (x0 - 1, y0 + 1), (x0 - 0, y0 + 0), (x0 + 1, y0 - 1)))
                whites.add(((x0 - 2, y0 + 2), (x0 - 1, y0 + 1), (x0 - 0, y0 + 0), (x0 + 1, y0 - 1), (x0 + 2, y0 - 2)))
                whites.add(((x0 - 1, y0 + 1), (x0 - 0, y0 + 0), (x0 + 1, y0 - 1), (x0 + 2, y0 - 2), (x0 + 3, y0 - 3)))
                whites.add(((x0 - 0, y0 + 0), (x0 + 1, y0 - 1), (x0 + 2, y0 - 2), (x0 + 3, y0 - 3), (x0 + 4, y0 - 4)))

        # ----- 整理获胜方案 -----
        black_need1 = set()  # 黑色需要1个即可获胜
        black_need2 = set()  # 黑色需要2个即可获胜
        white_need1 = set()  # 白色需要1个即可获胜
        for choice in blacks:
            black_num = white_num = 0
            for x0, y0 in choice:
                if (x0, y0) in already_black:
                    black_num += 1
                if (x0, y0) in already_white:
                    white_num += 1
                    break
            if white_num > 0:  # 如果已经有白色则跳过
                continue
            if black_num == 3:
                black_need2.add(choice)
            if black_num == 4:
                black_need1.add(choice)

        for choice in whites:
            black_num = white_num = 0
            for x0, y0 in choice:
                if (x0, y0) in already_black:
                    black_num += 1
                    break
                if (x0, y0) in already_white:
                    white_num += 1
            if black_num > 0:  # 如果已经有黑色则跳过
                continue
            if white_num == 4:
                white_need1.add(choice)

        # print('黑方1步获胜:', black_need1)
        # print('黑方2步获胜:', black_need2)
        # print('白方1步获胜:', white_need1)

        # ----- [获胜:1步] 如果黑色只需要一步即可获胜，则黑方必胜 -----
        if len(black_need1) > 0:
            return 'Black'

        # ----- 枚举白色一步即可获胜的点数量 -----
        white_win_point = set()
        for choice in white_need1:
            for x0, y0 in choice:
                if (x0, y0) not in already_white:
                    white_win_point.add((x0, y0))
        # print("白方一步获胜的点:", white_win_point)

        # ----- [获胜:2步] 如果白方有超过一种获胜方法，则白方必胜 -----
        if len(white_win_point) > 1:
            return 'White'

        # ----- [平局] 如果黑方没有2步获胜方法，则平局 -----
        if len(black_need2) == 0:
            return 'None'

        # ----- 枚举黑色两步即可获胜的点组合 -----
        black_win_group = set()
        for choice in black_need2:
            group = []
            for x0, y0 in choice:
                if (x0, y0) not in already_black:
                    group.append((x0, y0))
            black_win_group.add(tuple(sorted(group)))

        # print("黑色两步获胜的点组合:", black_win_group)

        # ----- 处理白方有一种获胜方法，黑方第1步必须堵白方获胜机会的情况 -----
        if len(white_win_point) == 1:
            x1, y1 = white_win_point.pop()  # 黑棋第1步的位置

            # 枚举此时黑方仍剩余的获胜点数量
            win_black_point = set()
            for (point1, point2) in black_win_group:
                if (x1, y1) == point1:
                    win_black_point.add(point2)
                    continue
                if (x1, y1) == point2:
                    win_black_point.add(point1)
            # print("黑色第3步获胜的点:", win_black_point)

            # 如果此时黑方仍剩余超过1个获胜点，则黑方胜利，反之平局
            if len(win_black_point) > 1:
                return 'Black'
            else:
                return 'None'

        # ----- 处理白方没有获胜方法，黑方第1步用于尝试获胜的情况 -----
        else:
            # 黑方所有可以选择的点
            choose = set()
            for (point1, point2) in black_win_group:
                choose.add(point1)
                choose.add(point2)

            # 黑方遍历考虑选择每一种获胜方案
            for x1, y1 in choose:
                # 枚举此时黑方仍剩余的获胜点数量
                win_black_point = set()
                for (point1, point2) in black_win_group:
                    if (x1, y1) == point1:
                        win_black_point.add(point2)
                        continue
                    if (x1, y1) == point2:
                        win_black_point.add(point1)
                # print("黑色第3步获胜的点:", win_black_point)

                # 如果此时黑方仍剩余超过1个获胜点，则黑方胜利，反之平局
                if len(win_black_point) > 1:
                    return 'Black'

            return 'None'


if __name__ == "__main__":
    # "None"
    print(Solution().gobang(pieces=[[0, 0, 1], [1, 1, 1], [2, 2, 0]]))

    # "Black"
    print(Solution().gobang(
        pieces=[[1, 2, 1], [1, 4, 1], [1, 5, 1], [2, 1, 0], [2, 3, 0], [2, 4, 0], [3, 2, 1], [3, 4, 0], [4, 2, 1],
                [5, 2, 1]]))
